package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序：
 * 1.时间复杂度：
 *      O(n^2)
 *  2.空间复杂度：
 *      O(1)是原地排序算法
 * 3.算法稳定性：
 *     不是稳定排序算法
 */
public class SelectSort {

    /**
     * 选择排序
     * @param array：待排序数组
     * @param n：待排序数组大小
     */
    public static void sort(Integer [] array,int n) {
        // 如果排序数组规模小于等于1，直接返回
        if (n <= 1) {
            return;
        }

        // 将待排序数组，分为：有序区间、无序区间
        // 一开始，假设整个序列都无序，那么有序区间的元素个数是：0，无序区间的元素个数是：n
        // 每次从无序区间中，选择最小元素，插入有序区间末尾：n个元素，n次选择
        for(int i = 0; i < n; i++){

            // 从无序区间第一个位置开始查找：最小元素位置
            int min = i;
            for(int j = i+1; j < n; j++){
                // 比较大小，设定新的最小元素位置标记
                if(array[min] > array[j]){
                    min = j;
                }
            }

           // 找到新的最小元素位置后，进行数据交换
            System.out.println("第【" + (i+1) + "】次选择，最小元素是：" + array[min]);
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;

        }

    }
}
